import java.util.HashMap;
import java.util.Map;

public class LeetCode138 {

    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    Map<Node, Node> cachedMap = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        if (!cachedMap.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedMap.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedMap.get(head);
    }

    public Node copyRandomList1(Node head) {
        if (head == null) {
            return head;
        }
        Node dummy = new Node(-1);
        dummy.next = head;
        while (head != null) {
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        head = dummy.next;
        while (head != null) {
            head.next.random = head.random != null ? head.random.next : null;
            head = head.next.next;
        }
        head = dummy.next;
        Node ans = head.next;
        while (head != null) {
            Node tmp = head.next;
            head.next = head.next != null ? head.next.next : null;
            head = tmp;
        }
        return ans;
    }

}
